package 链表.分隔链表;

import java.util.List;

/**
 * @author: wh(1835734390 @ qq.com)
 * @date: 2023/5/12 16:57
 * @description:
 * @version:
 */

/**
 * 给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。
 * 你应当 保留 两个分区中每个节点的初始相对位置。
 */
public class Solution {
    public static void main(String[] args) {
        ListNode head = new ListNode(1,new ListNode(4,new ListNode(3,new ListNode(2,new ListNode(5,new ListNode(2))))));
        System.out.println(partition(head, 3));
    }

    public static ListNode partition(ListNode head, int x) {
        ListNode root2 = new ListNode(-1);
        ListNode r = root2;
        root2.next = null;
        ListNode root1 = new ListNode(-1);
        root1.next = head;
        ListNode pre = root1;
        ListNode p = head;
        //把所有小于x值得链表组合成一条新的链表。
        while (p != null) {
            ListNode q = p.next;
            if (p.val < x) {
                pre.next = p.next;
                p.next = null;
                r.next = p;
                r = r.next;
                p = q;
            } else {
                pre = pre.next;
                p = q;
            }
        }
        r.next = root1.next;
        return root2.next;
    }
}
